package org.mountainpunch.ds.sparsematrix;

import java.util.Formatter;
import java.util.Locale;

/**
 * A generic SparseMatrix which is {@link Iterable<T>}. A SparseMatrix is
 * treated like Collection and only stores elements in it. In order to perform
 * arithmetic operations on them, please look at {@link SparseMatrixUtils}.
 *
 * @author siddharth
 */
public class SparseMatrix<T> implements Iterable<T> {

  private int _rows, _cols;
  private MatrixEntry<T>[] _terms ;

  /**
   * Creates an empty SparseMatrix.
   */
  public SparseMatrix() {
    this(0, 0, null);
  }

  /**
   * Creates a SparseMatrix with a given parameterized data type.
   * @param rows the number of rows in the matrix.
   * @param cols the number of columns in the matrix.
   * @param terms the MatrixEntry parameterized with the given data type {@link MatrixEntry}.
   *
   */
  public SparseMatrix(int rows, int cols, MatrixEntry<T>[] terms) {
    _rows = rows;
    _cols = cols;
    _terms = terms;
  }

  /**
   * Transposes the matrix. This method has a naive implementation with the O(rows*terms).
   * @return the transposed matrix.
   */
  public SparseMatrix<T> transpose() {
    MatrixEntry<T>[] resultTerms = emptyArray(_terms.length) ;

    if (_terms.length > 0) {
      int currentB = 0;
      for (int c = 0; c < _cols; c++) {
        for (int i = 0; i < _terms.length; i++) {

          if (_terms[i].getCol() == c) {
            MatrixEntry<T> matrixEntry = new MatrixEntry<T>();
            matrixEntry.setRow(c);
            matrixEntry.setCol(_terms[i].getRow());
            matrixEntry.setValue(_terms[i].getValue());

            resultTerms[currentB]= matrixEntry;

            currentB++;
          }
        }
      }
    }

    return new SparseMatrix<T>(_rows, _cols, resultTerms);
  }

  /**
   * Creates an empty array of MatrixEntries.
   * @param capacity the number of elements in the array object.
   * @return the parameterized array object.
   */
  private MatrixEntry<T>[] emptyArray(int capacity) {
    MatrixEntry<T>[] matArr ;
    matArr = (MatrixEntry<T>[]) java.lang.reflect.Array.newInstance(MatrixEntry.class, capacity);
    for (int i = 0; i < matArr.length; i++) {
      matArr[i] = new MatrixEntry<T>();
    }
    return matArr;
  }

  /**
   * Creates a transpose of the matrix. This implementation is an improvement over the naive
   * implementation of the transpose and has time complexity of O(rows + terms).
   * @return the transposed matrix.
   */
  public SparseMatrix<T> fastTranspose() {
    int[] rowSize = new int[_cols];
    int[] rowStart = new int[_cols];

    MatrixEntry<T>[] bterms = emptyArray(_terms.length);

    if (_terms.length > 0) {
      //Initialize.
      for (int i = 0; i < _cols; i++) {
        rowSize[i] = 0;
      }

      for (int i = 0; i < _terms.length; i++) {
        rowSize[_terms[i].getCol()]++;
      }

      rowStart[0] = 0;
      for (int i = 1; i < _cols; i++) {
        rowStart[i] = rowStart[i - 1] + rowSize[i - 1];
      }

      for (int i = 0; i < _terms.length; i++) {
        int j = rowStart[_terms[i].getCol()];
        MatrixEntry<T> matrixEntry = new MatrixEntry<T>();

        matrixEntry.setRow(_terms[i].getCol());
        matrixEntry.setCol(_terms[i].getRow());
        matrixEntry.setValue(_terms[i].getValue());

        bterms[j]= matrixEntry;

        rowStart[_terms[i].getCol()]++;
      }
    }

    rowSize = null;
    rowStart = null;
    return new SparseMatrix<T>(_rows, _cols, bterms);
  }

  /**
   * Gets the number of rows for this matrix.
   * @return the number of rows.
   */
  public int getNumRows() {
    return _rows;
  }

  /**
   * Gets the number of Columns for this matrix.
   * @return the number of cols.
   */
  public int getNumCols() {
    return _cols;
  }

  /**
   *
   * {@inheritDoc }
   */
  @Override
  public SparseMatrixIterator<T> iterator() {
    return new SparseMatrixIteratorImpl<T>(_terms);
  }

  /**
   * Gets the number of non-zero elements in the sparse matrix.
   * @return the number of non-zero elements in the sparse matrix.
   */
  public int size() {
    if(_terms != null) {
      return _terms.length;
    }

    return 0;
  }

  /**
   * Checks if this sparse matrix is empty.
   * @return true if matrix has no elements, false otherwise.
   */
  public boolean isEmpty() {
    return _terms == null ;
  }

  /**
   * prints the terms with row, col, values within this matrix.
   */
  public void printTerms() {
    System.out.println("using Iterator: ");
    StringBuilder sbuilder = new StringBuilder();
    Formatter formatter = new Formatter(sbuilder, Locale.US);
    formatter.format("%1$2s %2$10s %3$10s %4$10s \n", "No.", "Row", "Col", "Value");
    SparseMatrixIterator<T> iter = iterator() ;
    int idx = 0;
    while(iter.hasNext()) {
      T elem = iter.next();
      int row = iter.getRow();
      int col = iter.getCol();
      formatter.format("%1$2s %2$10s %3$10s %4$10s \n", idx++, row, col, elem);
    }

    System.out.println(sbuilder.toString());
  }
}
